package main

import (
	"container/list"
	"fmt"
)

//树的后序遍历

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归
func postOrder1(root *TreeNode) (res []int) {
	var post func(*TreeNode)
	post = func(node *TreeNode) {
		if node == nil {
			return
		}
		post(node.Left)             //左
		post(node.Right)            //右
		res = append(res, node.Val) //中 （后序 后就是第三步即最后一步实现）
	}
	post(root)
	return
}

// postOrder2
//非递归（迭代）借助栈
//对于后序遍历（左右中）
//前序遍历是中->左->右 先调换左右顺序变成中->右->左 再对结果数组进行反转即变成左->右->中
func postOrder2(root *TreeNode) (res []int) {
	if root == nil {
		return
	}
	var stack = list.New()
	//前序遍历压栈顺序 调换左右入栈顺序
	stack.PushBack(root.Left)   //左
	stack.PushBack(root.Right)  //右
	res = append(res, root.Val) //中
	for stack.Len() > 0 {
		e := stack.Back()
		stack.Remove(e)
		node := e.Value.(*TreeNode) //类型断言
		if node == nil {
			continue
		}
		res = append(res, node.Val)
		stack.PushBack(node.Left)
		stack.PushBack(node.Right)
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-i-1] = res[len(res)-i-1], res[i]
	}
	return res
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}
	//fmt.Println(postOrder1(A))
	fmt.Println(postOrder2(A))
}
